#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

class Solution{
    public:
    int ans1(vector<int>& nums){
        int len = nums.size();
        if(len == 1){
            return nums[0];
        }
        if(len == 2){
            return max(nums[0], nums[1]);
        }
        vector<int> dp(len+1);
        dp[0] = 0;
        dp[1] = nums[0];
        dp[2] = nums[1];
        for(int i = 3; i != len+1; i++){
            dp[i] = nums[i-1] + max(dp[i-2], dp[i-3]);
        }

        int max_val = *max_element(dp.begin(), dp.end());
        return max_val;
    }
};

void test1(){
    Solution s;
    vector<int> nums = {1,2,3,1};

    int ret = s.ans1(nums);
    cout << ret << endl;
}

void test2(){
    Solution s;
    vector<int> nums = {2,7,9,3,1};

    int ret = s.ans1(nums);
    cout << ret << endl;
}


int main(void){
    test1();
    test2();

    return 0;
}